 /*Universidad del Valle de Guatemala
*Hoja de Trabajo 9
*Integrantes:
*   Mayra Yucely Beb Caal Carne: 12537
*   Victor Fuentes Aruajo Carne: 12128
*/
/*
*
  *  codigo tomado de:Yimy Juarez 
 *        Gustavo Castro
*          Ulil Cojti
  *https://code.google.com/p/hoja-trabajo-8/source/browse/#svn%2Ftrunk%2Fhoja8%2Fsrc%2Fhoja8*/

import java.util.*;

public class Graph {

        protected Vector<Node> Nodes = new Vector<Node>();
        protected Vector<Edge> Edges = new Vector<Edge>();
        protected boolean Directed = false;
        protected boolean sortedNEighbors = false;
        protected double[][] math;
        
        //metodo para botener la matriz de adyadencia
        public double[][] getAdjacencyMatrix() {
                double[][] adjMatrix = new double[Nodes.size()][Nodes.size()];
                
                for(int i = 0; i < Nodes.size(); i++)
                        for(int j = 0; j < Nodes.size(); j++)
                                if(i == j)
                                        adjMatrix[i][j] = 0;
                                else
                                        adjMatrix[i][j] = Double.POSITIVE_INFINITY;
                                
                for(int i = 0; i < Nodes.size(); i++) {
                        Node node = Nodes.elementAt(i);
                        //System.out.println("Current node: " + node);
                        
                        for(int j = 0; j < Edges.size(); j++) {
                                Edge edge = Edges.elementAt(j);
                                //System.out.println(edge.toString()+" "+edge.getWeight());
                                if(edge.x == node) {
                                        int indexOfNeighbor = Nodes.indexOf(edge.y);
                                        
                                        adjMatrix[i][indexOfNeighbor] = edge.peso;
                                }
                        }
                }
        //        imprimeMatriz(adjMatrix);
                
                return adjMatrix;
        }
        
        //impresion de matriz de pasos, o matriz de solo datos
        public void imprimeMatriz(double[][] adjMatrix){
            for(int i = 0; i < Nodes.size(); i++) {
                System.out.println();
                for(int j = 0; j < Nodes.size(); j++) 
                    {
                        System.out.printf("[%f]",adjMatrix[i][j]);
                    }
            }
            
        }
        //metodo para indicar que si ahy conexion entre nodos
        public void setDirected() {
                Directed = true;
        }
        
        //metodo para indicar que no hay conexion entre nodos
        public void setUndirected() {
                Directed = false;
        }
        
        //metodo para devolver la conexion entre nodos
        public boolean isDirected() {
                return Directed;
        } 
        
        public int indexOf(Node x) {
                for(int i = 0; i < Nodes.size(); i++)
                        if(Nodes.elementAt(i).data.equals(x.data))
                                return i;
                                
                return -1;
        }
        
        //metodo para obtener nodos
        public Vector<Node> getNodes() {
                return Nodes;
        }
        //metodo para obtener las aritas
        public Vector<Edge> getEdges() {
                return Edges;
        }
        
        //metodo para obtener algun nodo segun parametro de valor
        public Node getNodeAt(int i) {
                return Nodes.elementAt(i);
        }
        
        //metodo para obtener los vecinos de los ndoos
        public Vector<Node> getNeighbors(Node x) {
                Vector<Node> neighbors = new Vector<Node>();
                
                for(int i = 0; i < Edges.size(); i++) {
                        Edge edge = Edges.elementAt(i);
                        
                        if(edge.x == x)
                                neighbors.add(edge.y);
                                
                        if(!Directed && edge.y == x)
                                neighbors.add(edge.x);
                }
                
                if(sortedNEighbors)
                        Collections.sort(neighbors);
                
                return neighbors;
        }
            
        public int addNode(Node x) {
                Nodes.add(x);
                
                return Nodes.size() - 1;
        }
        
        public void addEdge(Edge x) {
                Edges.add(x);
                
                if(!Directed)
                        Edges.add(new Edge(x.y, x.x, x.peso));
        }
        
        public void printNodes() {
                System.out.println(Nodes);
        }
        
        public void printEdges() {
                System.out.println(Edges);
        }
        public void eliminaArista(String nodo1,String nodo2){
            Node x=null;
            Node y=null;
            int indice=0;
            for(int i=0;i<Nodes.size();i++){
                if(nodo1.equals(Nodes.get(i).toString()))
                   x=Nodes.get(i); 
                if(nodo2.equals(Nodes.get(i).toString()))
                   y=Nodes.get(i); 

            }
            for(int i=0;i<Edges.size();i++){
                if(x.equals(Edges.get(i).getOrigen()))
                {     
                    if(y.equals(Edges.get(i).getDestino()))
                           Edges.remove(i); 
                }   
            }                               
 
        }
        //metodo para obtener el nodo segun el nombre
        public Node getNodeByName(String name){
            for(int i=0;i<Nodes.size();i++)
                if(name.equals(Nodes.get(i).toString()))
                    return Nodes.get(i);
            return null;
        }
        public void setMatrixPath(double[][] mat){
            this.math = mat;
        }
        public double[][] getMatrixPath(){
            return this.math;
        }
        //metodo para construccion y ejecucion de algoritmo de floyd
        public int[][] floydReconstruction(double[][] matriz ){
            double matrix[][]  = matriz;            
            int next[][] = new int[matrix.length][matrix.length];
            
            for(int k=1;k<matrix.length;k++){
               for(int i=1;i<matrix.length;i++){
                   next[k][i]=k;                       
               }
            }            
            
            for(int k=1;k<matrix.length;k++){
               for(int i=1;i<matrix.length;i++){
                   for(int j=1;j<matrix.length;j++){
                       if((matrix[i][k]+matrix[k][j])<matrix[i][j]){
                           matrix[i][j]=matrix[i][k]+matrix[k][j];
                           next[i][j] = next[k][j];                           
                           next[j][i] = next[k][i];                                                      
                       }
                   }
               }
            }   
            setMatrixPath(matrix);
            return next;
        }
        public void path(int i,int j, int[][] next){
            if(i!=j){
                path(i,next[i][j],next);
            }
            System.out.print(getNodeAt(j)+" ");
        }
        
        
}